// 环形链表衍生问题——定位环的起点

import { ListNode } from '../types'

/**
 * 真题描述：
 * 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
 *
 * 示例 1：
 * 输入：head = [3,2,0,-4]（如下图） 输出：tail connects to node index 1
 * 解释：链表中有一个环，其尾部连接到第二个结点。
 *
 * 示例 2：
 * 输入：head = [1,2]（如下图）
 * 输出：tail connects to node index 0
 * 解释：链表中有一个环，其尾部连接到第一个结点。
 *
 * 示例 3：
 * 输入：head = [1]（如下图）
 * 输出：no cycle
 * 解释：链表中没有环。
 */

const detectCycle = function detectCycle(
	head: ListNode & { flag: boolean }
): ListNode | null {
	while (head) {
		if (head.flag) {
			return head as ListNode
		} else {
			head.flag = true
			head = head.next as ListNode & { flag: boolean }
		}
	}

	return null
}
